TIME COMPLEXITY

Papers with time complexity

BCTH: A Novel Text Hashing Approach via Bayesian Clustering (2020.aacl-main)

Copied to clipboard

Challenge:	Similarity search is a promising strategy to find the most similar items for a given query item.
Approach:	They propose to utilize Bayesian Clustering for Text Hashing to map documents to binary codes by utilizing multiple Bayessian Clusters in parallel.
Outcome:	The proposed approach is competitive compared with baselines in the perspective of precision and training speed.

Long-range Sequence Modeling with Predictable Sparse Attention (2022.acl-long)

Copied to clipboard

Yimeng Zhuang, Jing Zhang, Mei Tu

Language Models

Challenge:	Existing approaches to capture global context dependencies in sequence modeling suffer from quadratic complexity in time and memory usage.
Approach:	They propose an efficient Transformer architecture for fast long-range sequence modeling with a sparse attention matrix and a hidden state cross module.
Outcome:	The proposed architecture outperforms the standard multi-head attention and its variants in various long-sequence tasks with low computational costs.

No, you’re not alone: A better way to find people with similar experiences on Reddit (D19-55)

Copied to clipboard

Zhilin Wang, Elena Rastorgueva, Weizhe Lin, Xiaodong Wu

Text Clustering

Challenge:	a probabilistic clustering algorithm can help users find posts that discuss experiences similar to their own . a recent study shows that probabilistic Clustering can yield a better performance than baseline clustering methods .
Approach:	They propose a probabilistic clustering algorithm that can help Reddit users find posts that discuss experiences similar to their own.
Outcome:	The proposed algorithm can find posts that discuss experiences similar to their own . it performs better than baseline clustering methods due to high runtime overhead .

GloCOM: A Short Text Neural Topic Model via Global Clustering Context (2025.naacl-long)

Copied to clipboard

Quang Duc Nguyen, Tung Nguyen, Duc Anh Nguyen, Linh Ngo Van, Sang Dinh, Thien Huu Nguyen

Information Extraction & Text Mining

Challenge:	Existing neural topic models often overlook uncovering hidden topics from short texts due to data sparsity, poor aggregation quality, and difficulty in inferring topic proportions for individual documents.
Approach:	They propose a model which constructs global clustering contexts for short texts using text embeddings from pre-trained language models.
Outcome:	The proposed model outperforms state-of-the-art models on short texts in topic quality and document representation.

Neural Collective Entity Linking (C18-1)

Copied to clipboard

Yixin Cao, Lei Hou, Juanzi Li, Zhiyuan Liu

Knowledge Representation

Challenge:	Entity linking aims to link entity mentions in texts to knowledge bases, but existing methods rely on local contexts to resolve entities independently.
Approach:	They propose a neural model for collective entity linking that integrates local contextual features and global coherence information to improve the computation efficiency.
Outcome:	The proposed model improves its performance on five publicly available datasets and can be used to train on Wikipedia hyperlinks to avoid overfitting and domain bias.

Improving Coverage and Runtime Complexity for Exact Inference in Non-Projective Transition-Based Dependency Parsers (N18-2)

Copied to clipboard

Tianze Shi, Carlos Gómez-Rodríguez, Lillian Lee

Syntactic Text Processing

Challenge:	Non-projective dependency trees account for 12.59% of all training sentences in the annotated Universal Dependencies (UD) 2.1 data.
Approach:	They generalize Cohen et al.'s (2011) parser to a family of non-projective transition-based dependency parsers allowing polynomial-time exact inference.
Outcome:	The proposed system can be extended to include a variant that reduces time complexity to O(n6), improving over the known bounds in exact inference for non-projective transition-based parsing.

Large Language Model Evaluation via Matrix Nuclear-Norm (2025.findings-emnlp)

Copied to clipboard

Yahan Li, Tingyu Xia, Yuan Wu, Yi Chang

Semantic Text Processing

Challenge:	Large language models (LLMs) are computationally intensive due to their O(n3) time complexity with Singular Value Decomposition (SVD).
Approach:	They propose a metric to quantify the data compression proficiency of large language models and a convex approximation of matrix rank to capture both predictive discriminability and diversity.
Outcome:	The proposed model achieves speeds 8 to 24 times faster than Matrix Entropy for the CEREBRAS-GPT model as models increase from 111M to 6.7B .

Stack-Pointer Networks for Dependency Parsing (P18-1)

Copied to clipboard

Xuezhe Ma, Zecong Hu, Jingzhou Liu, Nanyun Peng, Graham Neubig, Eduard Hovy

Syntactic Text Processing

Challenge:	Existing approaches to dependency parsing are local and greedy transitionbased . StackPtr parsers use the information of whole sentences and previously derived subtree structures .
Approach:	They propose a stack-pointer network-based dependency parser that reads whole sentence and builds dependency tree top-down in a depth-first fashion.
Outcome:	The proposed model reads and encodes whole sentence, then builds dependency tree top-down (from root-to-leaf) in a depth-first fashion.

Prompt-based Text Entailment for Low-Resource Named Entity Recognition (2022.coling-1)

Copied to clipboard

Dongfang Li, Baotian Hu, Qingcai Chen

Low-Resource NLP

Challenge:	Pre-trained Language Models (PLMs) have been applied in NLP tasks but require labeled data for downstream tasks.
Approach:	They propose a method for low-resource named entity recognition that uses prompts to get entailment scores for each candidate and inject tagging labels into prompts.
Outcome:	The proposed method achieves competitive performance on the CoNLL03 dataset, and better than fine-tuned counterparts on the MIT Movie and Few-NERD datasets in low-resource settings.

Batch IS NOT Heavy: Learning Word Representations From All Samples (P18-1)

Copied to clipboard

Xin Xin, Fajie Yuan, Xiangnan He, Joemon M. Jose

Semantic Text Processing

Challenge:	Stochastic Gradient Descent with negative sampling is the most prevalent approach to learn word representations.
Approach:	They propose a method that uses batch gradient learning to generate word representations from all training samples.
Outcome:	The proposed method outperforms sampling-based methods on several benchmark tasks.

Locate and Label: A Two-stage Identifier for Nested Named Entity Recognition (2021.acl-long)

Copied to clipboard

Yongliang Shen, Xinyin Ma, Zeqi Tan, Shuai Zhang, Wen Wang, Weiming Lu

Information Extraction & Text Mining

Challenge:	Named entity recognition (NER) is a well-studied task in natural language processing.
Approach:	They propose a method that generates span proposals and labels them with categories . they use boundary information of entities and partially matched spans to locate them .
Outcome:	The proposed method outperforms state-of-the-art models on nested NER datasets.

Efficient Constituency Parsing by Pointing (2020.acl-main)

Copied to clipboard

Thanh-Tung Nguyen, Xuan-Phi Nguyen, Shafiq Joty, Xiaoli Li

Language Models

Challenge:	Constituency parsing is a core task in natural language processing (NLP) Existing methods for constituency paring are greedy transition-based or globally optimized.
Approach:	They propose a constituency parsing model that casts the problem into a series of pointing tasks.
Outcome:	The proposed model achieves 92.78 F1 without pre-trained models, which is faster than existing models.

Dynamic Programming in Rank Space: Scaling Structured Inference with Low-Rank HMMs and PCFGs (2022.naacl-main)

Copied to clipboard

Songlin Yang, Wei Liu, Kewei Tu

Multimodality

Challenge:	Hidden Markov Models (HMMs) and Probabilistic Context-Free Grammars (PCFGs) are widely used structured models.
Approach:	They use tensor rank decomposition to reduce computational complexities for a subset of FGGs subsuming HMMs and PCFGs.
Outcome:	The proposed model performs better on HMM modeling and unsupervised PCFG parsing than previous work.

Train Once for All: A Transitional Approach for Efficient Aspect Sentiment Triplet Extraction (2025.findings-emnlp)

Copied to clipboard

Xinmeng Hou, Lingyue Fu, Chenhao Meng, Kounianhua Du, Hai Hu

Sentiment Analysis

Challenge:	Existing approaches to extract aspects and opinions independently, optionally adding pairwise relations, often lead to error propagation and high time complexity.
Approach:	They propose a transition-based model that performs aspect and opinion extraction jointly and integrates contrastive-augmented optimization.
Outcome:	The proposed model outperforms previous models on two out of four datasets when trained on a single dataset.

R2D2: Recursive Transformer based on Differentiable Tree for Interpretable Hierarchical Language Modeling (2021.acl-long)

Copied to clipboard

Xiang Hu, Haitao Mi, Zujie Wen, Yafang Wang, Yi Su, Jing Zheng, Gerard de Melo

Language Models

Challenge:	Existing models with stacked layers do not explicitly model hierarchical structure of language understanding.
Approach:	They propose a recursive Transformer model based on differentiable CKY style binary trees to emulate hierarchical composition process.
Outcome:	The proposed model can predict words given their left and right abstraction nodes.

Sketching as a Tool for Understanding and Accelerating Self-attention for Long Sequences (2022.naacl-main)

Copied to clipboard

Yifan Chen, Qi Zeng, Dilek Hakkani-Tur, Di Jin, Heng Ji, Yun Yang

Language Models

Challenge:	Existing models for long sequences are not efficient due to the quadratic space and time complexity of the self-attention modules.
Approach:	They propose to reduce the quadratic complexity to linear (modulo logarithmic factors) by low-dimensional projection and row selection.
Outcome:	The proposed methods outperform transformer-based models with smaller time/space footprint on the Long Range Arena benchmark.

Copied to clipboard

Tomoyuki Jinno, Kazuki Hayashi, Yusuke Sakai, Hidetaka Kamigaito, Taro Watanabe

Semantic Text Processing

Challenge:	Existing knowledge probes for pre-trained language models exhibit quadratic time complexity, limiting the size of knowledge graphs used for probing.
Approach:	They propose an embedding-based relational probe that evaluates pre-trained language models' factual knowledge retrieval capabilities.
Outcome:	The proposed probe achieves effective time complexity of linear order O(n), supports rank-based evaluation metrics including Hit@k, handles multi-token entity names and enables probing whilst disambiguating homographic tail-entity names.

Multi-level Community-awareness Graph Neural Networks for Neural Machine Translation (2022.coling-1)

Copied to clipboard

Binh Nguyen, Long Nguyen, Dien Dinh

Semantic Text Processing

Challenge:	Recent studies have used Graph Neural Networks (GNNs) to encode language knowledge into token embeddings.
Approach:	They propose a multi-level community-awareness Graph Neural Network layer to jointly model local and global relationships between words and their linguistic roles in multiple communities.
Outcome:	The proposed method reduces time complexity in very long sentences while preserving the original meaning.

Large Language Model-Based Event Relation Extraction with Rationales (2025.coling-main)

Copied to clipboard

Zhilei Hu, Zixuan Li, Xiaolong Jin, Long Bai, Jiafeng Guo, Xueqi Cheng

Language Models

Challenge:	Existing methods for ERE rely on large language models, but they face limitations.
Approach:	They propose an LLM-based approach with rationales for the ERE task . LLMERE transforms ERE into a question-and-answer task that may have multiple answers .
Outcome:	Experimental results show that LLMERE improves over existing methods.

SwiftPrune: Hessian-Free Weight Pruning for Large Language Models (2025.findings-emnlp)

Copied to clipboard

Yuhan Kang, Yang Shi, Mei Wen, Jun He, Jianchao Yang, Zeyu Xue, Jing Feng, Xinwang Liu

Semantic Text Processing

Challenge:	a novel post-training pruning method relies on the Hessian matrix to perform pruning . current pruning methods are computationally intensive and lack performance due to second-order derivative calculations.
Approach:	They propose a Hessian-free weight pruning method that reduces computational burden . they use an Exponentially Weighted Moving Average technique to bypass weight sorting .
Outcome:	The proposed method achieves hardware-efficient model compression by eliminating computational intensive calculations.

High-order Joint Constituency and Dependency Parsing (2024.lrec-main)

Copied to clipboard

Yanggan Gu, Yang Hou, Zhefeng Wang, Xinyu Duan, Zhenghua Li

Syntactic Text Processing

Challenge:	Syntactic parsing aims to reveal how sentences are syntactically structured.
Approach:	They propose to produce compatible constituency and dependency trees simultaneously for input sentences . they adopt a much more efficient decoding algorithm and explore joint modeling at training phase .
Outcome:	The proposed model significantly improves matching ratio of whole trees compared to separate models . the proposed model adopts a much more efficient decoding algorithm .

Focus Your Attention (with Adaptive IIR Filters) (2023.emnlp-main)

Copied to clipboard

Shahar Lutati, Itamar Zimerman, Lior Wolf

Challenge:	Existing methods to deal with long-range data processing are implicit convolutions and regularized parameterization.
Approach:	They propose a new layer where dynamic (i.e., input-dependent) IIR filters are used to process the input sequence prior to applying conventional attention.
Outcome:	The proposed layer performs on-par with state-of-the-art networks with a fraction of their parameters and time complexity that is sub-quadratic with input size.